Branch and Bound

释义 Definition

“分支定界（法）”：一种用于组合优化与整数规划的求解方法。它把问题分解成许多子问题（branch，分支），并用已知的上界/下界（bound，界）来判断某些分支不可能产生更优解，从而剪枝，减少搜索量。（在不同语境下也可泛指“分支+界限剪枝”的系统搜索策略。）

发音 Pronunciation (IPA)

/ˌbræntʃ ən ˈbaʊnd/

例句 Examples

We used branch and bound to find the best schedule.
我们用分支定界法找到了最佳排程。

Branch and bound can solve some integer programming problems efficiently by pruning branches with poor bounds.
分支定界法可以通过剪去界限很差的分支，高效地求解一些整数规划问题。

词源 Etymology

该术语源自运筹学与算法领域对“搜索树”的形象描述：branch 指把问题切分成不同分支继续探索；bound 指利用已计算出的目标函数上界/下界来“定界”，当某分支不可能优于当前最优解时就停止展开。作为系统方法在20世纪中期的优化研究中逐步定型并普及。

相关词 Related Words

• Backtracking
• Pruning
• Optimization
• Integer Programming
• Mixed-Integer Programming
• Constraint Programming
• Search Tree
• Heuristic

文献作品 Literary Works

• Integer and Combinatorial Optimization（Nemhauser & Wolsey）——系统讨论整数规划与分支定界思想
• Combinatorial Optimization: Algorithms and Complexity（Papadimitriou & Steiglitz）——介绍组合优化中的相关算法框架
• The Traveling Salesman Problem: A Computational Study（Applegate, Bixby, Chvátal, Cook）——在旅行商问题的计算研究中使用分支定界/剪枝策略